#include <bits/stdc++.h>
using namespace std;

// 【题目】503. 下一个更大元素 II
// 【难度】中等
// 【提交】2025.9.25 https://leetcode.cn/problems/next-greater-element-ii/submissions/665889907
// 【标签】单调栈
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n,-1);
        stack<int> stk;

        for(int i = 2 * n - 1; i >= 0; i--){
            while(!stk.empty() && nums[i % n] >= stk.top()){
                stk.pop();
            }
            if(i < n && !stk.empty()){
                ans[i % n] = stk.top();
            }

            stk.push(nums[i % n]);        
        }
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 又学一招，取模实现两次遍历 
*/


/*
--------------------------------------------------------------------------------------------------------------
（学习笔记：LeetCode 503「下一个更大元素 II」
（提交记录：2024-03-25，C++，用时 18 ms，内存 7.5 MB）

一、题意与模型
给定一个循环数组 nums，要求找到每个元素的下一个更大的元素。循环数组意味着数组的最后一个元素与第一个元素相邻。因此，我们需要找出每个元素在数组中遍历顺序后的下一个更大元素。如果不存在下一个更大元素，则返回 -1。

二、标准 DP 状态设计
设 nextGreater[i] 为 nums[i] 的下一个更大元素。
利用栈来维护单调性，栈中的元素按递减顺序排列，帮助我们高效地找到每个元素的下一个更大元素。
需要考虑循环数组的特点，可以通过将数组遍历两遍来模拟循环。

三、你的实现思路
模拟循环数组：通过遍历 2 * n - 1 到 0 来模拟数组的循环访问，确保每个元素都能在数组中被访问两次。
栈操作：利用栈来存储元素的值，栈保持递减顺序。每当遇到一个较大的元素时，将栈中比它小的元素弹出，并更新它们的下一个更大元素。
结果计算：在遍历过程中，更新每个元素的下一个更大元素。

四、逐行注释（带细节提醒）
cpp

class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size(); // 获取数组的大小
vector<int> ans(n, -1); // 初始化结果数组，默认值为 -1
stack<int> stk; // 用栈来维护元素的递减顺序

php

    // 遍历两轮，模拟循环数组的效果
    for (int i = 2 * n - 1; i >= 0; i--) {
        // 弹出栈中所有比当前元素小的元素
        while (!stk.empty() && nums[i % n] >= stk.top()) {
            stk.pop();   // 弹出栈顶元素
        }

        // 只对前 n 个位置赋值，后 n 个位置是为了模拟循环
        if (i < n && !stk.empty()) {
            ans[i % n] = stk.top();  // 更新下一个更大元素
        }

        // 将当前元素压入栈中
        stk.push(nums[i % n]);
    }
    return ans;  // 返回结果数组
}
};

五、正确性证明
由于每个元素最多被入栈和出栈一次，因此栈的操作是 O(1) 的，保证了算法的高效性。
遍历两次数组，可以确保每个元素都能正确处理。通过 i % n 的方式，模拟了循环数组的效果。
栈中的元素始终保持递减顺序，确保每次计算下一个更大元素时是准确的。

六、复杂度
时间：O(n)，每个元素最多进栈和出栈一次，遍历两遍数组，因此时间复杂度为 O(n)。
空间：O(n)，栈和结果数组都需要存储 n 个元素。

七、优缺点分析
优点：
时间复杂度为 O(n)，非常高效，能够处理大规模数据。
使用栈保证了每个元素的下一个更大元素可以在 O(1) 时间内找到。

缺点：
栈的操作较为复杂，理解起来有一定难度，特别是对于循环数组的处理。
虽然时间复杂度是 O(n)，但代码实现相对较为复杂，需要较强的栈的操作理解。

八、改进建议
该算法的时间复杂度已经是最优的 O(n)，不需要进一步优化。
对栈的操作可以进行注释和分解，增强代码的可读性，尤其是栈顶元素弹出和更新操作。

九、一句话总结
该题通过模拟两轮遍历和栈的应用，高效地解决了循环数组中每个元素的下一个更大元素问题，时间复杂度为 O(n)，是该问题的最优解法，但代码实现对栈的使用需要一定的理解。
--------------------------------------------------------------------------------------------------------------
*/